#include <iostream>
#include <stack>
#include <vector>
#include "../head/struct.h"

using namespace std;

struct Command{
	string s;
	TreeNode* node;
	Command(string s, TreeNode* node): s(s), node(node){}
};
// 144
/**
 * 二叉树的前序遍历，使用栈非递归遍历
 * 时间复杂度: O(n), n为树的节点个数
 * 空间复杂度: O(h), h为树的高度	
 */
class Solution {
public:
	vector<int> postorderTraversal(TreeNode* root) {
		vector<int> res;
		if(root == NULL)
			return res;
		
		stack<Command> stack;
		stack.push(Command("go", root));
		while(!stack.empty()){
			// 取出栈顶的元素
			Command Command = stack.top();
			stack.pop();
			
			if(command.s == "print")
                res.push_back(command.node->val);
            else{
                assert(command.s == "go");
                stack.push(Command("print", command.node));
                if(command.node->right)
                    stack.push(Command("go",command.node->right));
                if(command.node->left)
                    stack.push(Command("go",command.node->left));
            }
			return res;
		}
	}
};

int main(){}
